class Solution
{
public:
    int maxProduct(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }
        vector<int> f(n, 0);
        vector<int> g(n, 0);
        f[0] = nums[0];
        g[0] = nums[0];
        int ret = INT_MIN;
        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i];
            g[i] = nums[i];
            if (nums[i] > 0)
            {
                f[i] = max(f[i], f[i - 1] * nums[i]);
                g[i] = min(g[i], g[i - 1] * nums[i]);
            }
            else
            {
                f[i] = max(f[i], g[i - 1] * nums[i]);
                g[i] = min(g[i], f[i - 1] * nums[i]);
            }
        }
        for (int i = 0; i < n; i++)
        {
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

//空间优化版本O（1）
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        if(n==1)
        {
            return nums[0];
        }
        int prev1=nums[0];
        int prev2=nums[0];
        int ret=INT_MIN;
        int cur1,cur2;
        for(int i=1;i<n;i++)
        {
            cur1=nums[i];
            cur2=nums[i];
            if(nums[i]>0)
            {
                cur1=max(cur1,prev1*nums[i]);
                cur2=min(cur2,prev2*nums[i]);
            }
            else
            {
                cur1=max(cur1,prev2*nums[i]);
                cur2=min(cur2,prev1*nums[i]);
            }
            prev1=cur1;
            prev2=cur2;
            ret=max(ret,cur1);
        }
        //循环从第2个元素开始 可能第一个元素就是最大值
        //也可以初始化得时候初始化为第一个元素
        ret=max(ret,nums[0]);
      
        return ret;
    }
};